package com.mayajie.tree;

/**
 * 树的存储结构-孩子链表表示法
 * @author mayajie
 * @date 2021/10/28
 */
public class ChildChainStruct {
    class Node {
        int child;
        Node next;

        Node(int child, Node next) {
            this.child = child;
            this.next = next;
        }
    }
    class HeadNode {
        Object data;
        Node firstChild;

        HeadNode(Object data, Node firstChild) {
            this.data = data;
            this.firstChild = firstChild;
        }
    }
    class HeadWithParentNode {
        Object data;
        int parent;
        Node firstChild;

        HeadWithParentNode(Object data, int parent, Node firstChild) {
            this.data = data;
            this.parent = parent;
            this.firstChild = firstChild;
        }
    }

    /**
     * 头结点不带双亲
     *     H
     *    / \
     *   A   C
     *  / \
     * B   E
     *    /|\
     *   G F D
     * @return
     */
    public HeadNode[] create1() {
        HeadNode[] tree = new HeadNode[8];
        tree[0] = new HeadNode('H', null);
        tree[1] = new HeadNode('A', null);
        tree[2] = new HeadNode('C', null);
        tree[3] = new HeadNode('B', null);
        tree[4] = new HeadNode('E', null);
        tree[5] = new HeadNode('G', null);
        tree[6] = new HeadNode('F', null);
        tree[7] = new HeadNode('D', null);

        tree[0].firstChild = new Node(1, new Node(2, null));
        tree[1].firstChild = new Node(3, new Node(4, null));
        tree[4].firstChild = new Node(5, new Node(6, new Node(7, null)));
        return tree;
    }

    /**
     * 头结点带双亲
     *     H
     *    / \
     *   A   C
     *  / \
     * B   E
     *    /|\
     *   G F D
     * @return
     */
    public HeadWithParentNode[] create2() {
        HeadWithParentNode[] tree = new HeadWithParentNode[8];
        tree[0] = new HeadWithParentNode('H', -1, null);
        tree[1] = new HeadWithParentNode('A', 0, null);
        tree[2] = new HeadWithParentNode('C', 0, null);
        tree[3] = new HeadWithParentNode('B', 1, null);
        tree[4] = new HeadWithParentNode('E', 1, null);
        tree[5] = new HeadWithParentNode('G', 4, null);
        tree[6] = new HeadWithParentNode('F', 4, null);
        tree[7] = new HeadWithParentNode('D', 4, null);

        tree[0].firstChild = new Node(1, new Node(2, null));
        tree[1].firstChild = new Node(3, new Node(4, null));
        tree[4].firstChild = new Node(5, new Node(6, new Node(7, null)));
        return tree;
    }

    public static void main(String[] args) {
        new ChildChainStruct().create1();
        new ChildChainStruct().create2();
    }
}
